package Queue;

/**
 *  题目 ：设计循环双端队列
 *  题目详述 ：
 *  设计实现双端队列。
 *
 * 实现 MyCircularDeque 类:
 *
 * MyCircularDeque(int k)：构造函数,双端队列最大为 k 。
 * boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true，否则返回 false 。
 * boolean insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true，否则返回 false 。
 * boolean deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true，否则返回 false 。
 * boolean deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true，否则返回 false 。
 * int getFront())：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
 * int getRear()：获得双端队列的最后一个元素。如果双端队列为空，返回 -1 。
 * boolean isEmpty()：若双端队列为空，则返回true，否则返回 false 。
 * boolean isFull()：若双端队列满了，则返回true，否则返回 false 。
 *
 */
public class CircularDeque {
    /**
     * 方法一 ： 使用数组模拟双端队列
     * 核心问题 ：
     * 在于如何区分 队列为空，和队列为满的情况；
     */

    // 定义front，指向双端队列的队列头部元素；
    // 定义rear，指向双端队列的队列尾部元素的下一个索引
            /*
    private int front;
    private int rear;
    private int DequeLength; // 获取双端队列的长度
    private int[] Deque; // 数组，模拟双端队列

    public CircularDeque(int k) {
        front = 0;
        rear = 0;
        DequeLength = k + 1; // 即，双端队列需要空出一个元素，用来区分 队列为空和 队列为满的情况；
        Deque = new int[DequeLength];
    }

    public boolean insertFront(int value) {
        if(isFull()){
            return false;
        }
        // 头指针指向的即为队列头部元素；即直接将头指针前移即可；
        front = (front - 1 + DequeLength) % DequeLength;
        Deque[front] = value;
        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()){
            return false;
        }
        // 尾指针指向的是队列尾元素的下一个索引，即先给尾指针插入元素后，再将尾指针后移
        Deque[rear] = value;
        rear = (rear + 1) % DequeLength;
        return true;
    }

    public boolean deleteFront() {
        if(isEmpty()){
            return false;
        }
        front = (front + 1) % DequeLength;
        return true;
    }

    public boolean deleteLast() {
        if(isEmpty()){
            return false;
        }
        rear = (rear - 1 + DequeLength) % DequeLength;
        // 特殊情况 ：即，rear为负数，需要通过将其加上DequeLength（数组长度），避免此情况的出现
        return true;
    }

    public int getFront() {
        if(isEmpty()){
            return -1;
        }
        return Deque[front];
    }

    public int getRear() {
        if (isEmpty()){
            return -1;
        }
        return Deque[(rear - 1 + DequeLength) % DequeLength];
    }

    public boolean isEmpty() {
        return front == rear; // 若是队列头元素和队列为元素一致时，即队列为空
    }

    public boolean isFull() {
        return front == (rear + 1) % DequeLength;
        // 由于所定义的数组长度为 （队列长度 + 1）；
        // 即当队列满时，（尾指针rear + 1）% 数组长度 应该与头指针相重合
    }
    */

    /**
     *  方法二 ：使用 双向链表 模拟双端队列
     *
     *  注意 ：双向链表，来实现双端队列；（若不是双向链表的话，即，从队列尾部进行删除元素的操作很难实现）
     *  判断队列为空 ：链表长度size是否为空；
     *  判断队列已满 ：链表长度size是否为双端循环队列的长度；
     */

    // 头指针，指向双端循环队列的头元素
    private ListedNode1 head;
    // 尾指针，所指向的是双端队列的尾元素
    private ListedNode1 tail;
    private int DequeLength; // 双端循环队列的最大长度
    private int size; // 用来记录链表的长度


    public CircularDeque(int k) {
        // 初始化时，链表中没有节点，即头指针和尾指针不用指向具体的的节点（即，不用初始化）
        // 可以在之后插入元素时，对于头指针和尾指针进行初始化
        DequeLength = k;
        size = 0;
    }

    public boolean insertFront(int value) {
        if(isFull()){
            return false;
        }
        ListedNode1 node1 = new ListedNode1(value); // 新建链表节点
        if(isEmpty()){
            // 特殊情况 ：插入元素时，链表还未空，即链表中没有任何元素；
            // 由于队列是空队列，即只会向其中插入一个结点；所以不需要去定义第一个节点的next结点，previous结点；
            head = node1; // 头指针，直接指向队列中第一个元素
            tail = node1; // 尾指针，直接指向队列中最后一个元素
            head.previous = tail; // 头指针所指向的头结点，其的上一个结点为尾结点
            tail.next = head; // 尾结点所指向的尾结点，其的下一个结点为头结点
            size++;
            return true;
        }

        ListedNode1 tempNode = head; // 即，临时结点为链表之前的头结点；
        head.previous = node1; // 将node1节点连接到链表上
        head = node1; // 头指针前移
        head.next = tempNode; // 头指针（即，新插入的头结点），直接指向之前的头结点
        head.previous = tail;
        tail.next = head;
        size++;
        return true;
    }

    public boolean insertLast(int value) {
        if(isFull()){
            return false;
        }
        ListedNode1 node2 = new ListedNode1(value); // 新建链表节点
        if(isEmpty()){
            // 特殊情况 ：插入元素时，链表还未空，即链表中没有任何元素；
            head = node2; // 头指针的next指针，所指向队列中第一个元素
            tail = node2; // 尾指针直接指向队列中第一个元素
            head.previous = tail; // 头指针所指向的头结点，其的上一个结点为尾结点
            tail.next = head; // 尾结点所指向的尾结点，其的下一个结点为头结点
            size++;
            return true;
        }
        ListedNode1 tempNode = tail; // 即，临时结点为未在链表尾部插入尾结点时的尾结点
        tail.next = node2; // 将新建的node2节点连接到链表上
        tail = node2;  // 尾指针后移
        tail.previous = tempNode;
        tail.next = head;
        head.previous = tail;
        size++;
        return true;
    }

    public boolean deleteFront() {
        if (isEmpty()){
            return false; // 链表为空的话，不存在能够删除的头元素
        }
        head = head.next;
        // 头指针直接后移，即可实现删除链表头节点的功能
        // 即，等价于队列删除头元素；
        size--;
        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()){
            return false; // 链表为空的话，不存在能够删除的尾元素
        }
        // 若是链表不为空的话，即需要将尾指针指向所要删除元素的上一个结点
        tail = tail.previous;
        size--;
        return true;
    }

    public int getFront() {
        if (isEmpty()){
            return -1;
        }
        return head.value;
        // 由于头指针所指向的是双端循环队列的头元素的前一个索引；
        // 即，头指针并不是指向队列头元素，头指针所指向节点.next == 队列头元素
    }

    public int getRear() {
        if(isEmpty()){
            return -1;
        }
        return tail.value; // 由于尾指针的next指针所指向的节点是双端循环队列的尾部元素
    }

    public boolean isEmpty() {
        return size == 0; // 即，若是链表的长度为0的话，则双端循环队列为空；
    }

    public boolean isFull() {
        return size == DequeLength; // 即，若是链表的长度 等于 双端循环队列的最大长度，即双端循环队列已满
    }

    /**
     *  核心思想 ：
     *      在于使用双向链表，来模拟双端循环队列；
     */
    class ListedNode1{
        private ListedNode1 next;
        private ListedNode1 previous;
        private int value;
        public ListedNode1(int value){
            this.value = value;
        }
    }
}
